package com.lgedu.houswork10;

public class h102 {
    /**
     * 获得金矿最优收益
     * @param w 工人数量
     * @param n 可选金矿数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿储量
     * @return
     */
    //递归进行求解
    public static int getBestGoldMining(int w,int n,int[] p,int[] g){
        if (w ==0||n==0){
            return 0;
        }
        if (w<p[n-1]){
            return getBestGoldMining(w,n-1,p,g);
        }
        return Math.max(getBestGoldMining(w,n-1,p,g),getBestGoldMining(w-p[n-1],n-1,p,g) + g[n-1]);
    }

    /**
     * 获得金矿最优收益
     * @param w 工人数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿数量
     * @return
     */
    //递归做了很多重复的计算，当金矿越来越多，递归层次越来越深，重复调用也就越来越多，无谓的调用必然会降低程序的性能
    //利用双循环来填充一个二维数组，时间复杂度和空间复杂度都是O(nw)
    public static int getBestGoldMiningV2(int w,int[] p,int[] g){
        //创建表格
        int[][] resultTable = new int[g.length+1][w +1];
        //填充表格
        for (int i =1;i<= g.length;i++){
            for (int j=1;j<=w;j++){
                if (j<p[i-1]){
                    resultTable[i][j] = resultTable[i-1][j];
                }else{
                    resultTable[i][j] = Math.max(resultTable[i-1][j],resultTable[i-1][j-p[i-1]] + g[i-1]);
                }
            }
        }
        //返回最后1个格子的值
        System.out.println(w);
        return resultTable[g.length][w];
    }

    // 并不需要保存整个表格，无论金矿多少座，我们只保存1行的数据即可，在计算下一行时，要从右向左统计，把旧的数据一个一个替换掉
    //时间复杂度是O(nw) 空间复杂度是O(n)
    /**
     * 获得金矿最优收益
     *
     * @param w 工人数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿数量
     * @return
     */
    public static int getBestGoldMiningV3(int w,int[] p,int[] g){
        //创建当前结果
        int[] results = new int[w+1];
        //填充一维数组
        for (int i=1;i<= g.length;i++){
            for (int j=w;j>=1;j--){
                if (j>=p[i-1]){
                    results[j] = Math.max(results[j],results[j-p[i-1]] + g[i-1]);
                }
            }
        }
        //返回最后一个格子的值

        return results[w];
    }


    public static void main(String[] args) {
        int w = 10;
        int[] p = {5,5,3,4,3};
        int[] g = {400,500,200,300,350};
        System.out.println("最优收益：" + getBestGoldMiningV2(w,p,g));
    }
}
